package com.itheima.datastructure.RedBlackTree;

import org.w3c.dom.Node;

import static com.itheima.datastructure.RedBlackTree.RedBlackTree.Color.BLACK;
import static com.itheima.datastructure.RedBlackTree.RedBlackTree.Color.RED;


/*
红黑树特点
1.所有节点都有两种颜色：红色和黑色
2.所有null视为黑色
3.红色节点不能相邻
4.根节点是黑色
5.从根节点到任意一个叶子节点，路径中的黑色叶子节点数量相同
 */
public class RedBlackTree {
    enum Color{
        RED,BLACK;
    }
    private  Node root;
    private static class Node {
        int key;
        Object value;
        Node left;
        Node right;
        Node parent;
        Color color = RED;

        public Node(int key, Object value) {
            this.key=key;
            this.value=value;
        }

        //是否是左孩子
        boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        //叔叔节点
        Node uncle() {
            //无父亲无爷爷就没有叔叔
            if (parent == null || parent.parent == null) {
                return null;
            }
            if (parent.isLeftChild()) {
                return parent.parent.right;
            } else {
                return parent.parent.left;
            }
        }

        //兄弟节点
        Node sibling() {
            if (parent == null) {
                return null;
            }
            if (this.isLeftChild()) {
                return parent.right;
            } else {
                return parent.left;
            }
        }
    }
        //判断红黑颜色
    boolean isRed(Node node){
        return node!=null && node.color==RED;
    }

    boolean isBlack(Node node){
            return node==null || node.color==BLACK;
        }

    //右旋：粉色节点是要旋转的节点，黄色是子孩子，绿色是子孩子的子孩子
    private void rightRotate(Node pink){
            Node parent=pink.parent;
            Node yellow=pink.left;
            Node green=yellow.right;
            if(green!=null){
                green.parent=pink;
            }
            yellow.right=pink;
            yellow.parent=parent;
            pink.left=green;
            pink.parent=yellow;
            if(parent==null){
                root=yellow;
            }else if(parent.left==pink){
                parent.left=yellow;
            }else{
                parent.right=yellow;
            }
    }

    //左旋
    private void leftRotate(Node pink){
        Node parent=pink.parent;
        Node yellow=pink.right;
        Node green=yellow.left;
        if(green!=null){
            green.parent=pink;
        }
        yellow.left=pink;
        yellow.parent=parent;
        pink.right=green;
        pink.parent=yellow;
        if(parent==null){
            root=yellow;
        }else if(parent.right==pink){
            parent.right=yellow;
        }else{
            parent.left=yellow;
        }
    }

    public void put(int key,Object value){
        Node p=root;
        Node parent=null;
        while(p!=null){
            parent=p;
            if(key<p.key){
                p=p.left;
            }else if(p.key>key){
                p=p.right;
            }else{
                p.value=value;
                return;
            }
        }
        Node inserted=new Node(key,value);
        if(parent==null){
            root=inserted;
        }else if(key< parent.key){
            parent.left=inserted;
        }else{
            parent.right=inserted;
        }
        fixRedRed(inserted);
    }
    //解决红红相邻的问题
    void fixRedRed(Node x){
        //case1：插入的节点是根节点
        if(x==root){
            x.color=BLACK;
            return;
        }
        //case2：插入节点的父亲是黑色，无需调整
        if(isBlack(x.parent)){
            return;
        }
        /*
        case3:插入节点的父亲是红色
        1.父亲变为黑色，为了黑色平衡，叔叔也变成黑色
        2.祖父如果是黑色不变可能造成黑色不平衡，祖父也变成红色
        3.祖父变成红色也可能造成红红相邻，递归祖父
         */
        Node parent=x.parent;
        Node uncle=x.uncle();
        Node grandparent=parent.parent;
        if(isRed(uncle)){
            parent.color=BLACK;
            uncle.color=BLACK;
            grandparent.color=RED;
            fixRedRed(grandparent);
            return;
        }
        //case4：当红红相邻叔叔为黑时
        if(parent.isLeftChild() && x.isLeftChild()){ //LL
            parent.color=BLACK;
            grandparent.color=RED;
            rightRotate(grandparent);
        }else if(parent.isLeftChild() && !x.isLeftChild()){//LR
            //先变成LL
            leftRotate(parent);
            x.color=BLACK;
            grandparent.color=RED;
            rightRotate(grandparent);
        }else if(!parent.isLeftChild() && !x.isLeftChild()){
            parent.color=BLACK;
            grandparent.color=RED;
            leftRotate(grandparent);
        }else{
            rightRotate(parent);
            x.color=BLACK;
            grandparent.color=RED;
            leftRotate(grandparent);
        }
    }

    //删除操作
    public void remove(int key){
        Node deleted=find(key);
        if(deleted==null){
            return ;
        }
        doRemove(deleted);
    }
    //处理双黑
    private void fixDoubleBlack(Node x){
        if(x==root){
            return;
        }
        Node parent=x.parent;
        Node sibling= x.sibling();
        //case3：兄弟节点是红色
        if(isRed(sibling)){
            if(x.isLeftChild()){
                leftRotate(parent);
            }else{
                rightRotate(parent);
            }
            parent.color=RED;
            sibling.color=BLACK;
            fixDoubleBlack(x);//让新的兄弟变成黑色
            return;
        }
        if(sibling!=null){
            //case4:兄弟是黑色，两个侄子也为黑色
            if(isBlack(sibling.left) && isBlack(sibling.right)){
                sibling.color=RED;
                if(isRed(parent)){
                    parent.color=BLACK;
                }else{
                    fixDoubleBlack(parent);
                }
            }
            //case5:兄弟是黑色，侄子有红色
            else{
                //兄弟是左孩子，侄子是左孩子
                if(sibling.isLeftChild() && isRed(sibling.left)){
                    rightRotate(parent);
                    sibling.left.color=BLACK;
                    sibling.color= parent.color;

                }
                //LR
                else if(sibling.isLeftChild() && isRed(sibling.right)){
                    sibling.right.color= parent.color;
                    leftRotate(sibling);
                    rightRotate(parent);;
                }
                //RL
                else if(!sibling.isLeftChild() && isRed(sibling.left)){
                    sibling.left.color= parent.color;
                    rightRotate(sibling);
                    leftRotate(parent);
                //RR
                }else{
                    leftRotate(parent);
                    sibling.right.color= parent.color;
                    sibling.color= parent.color;
                }
                parent.color=BLACK;
            }
        } else{
            fixDoubleBlack(parent);
        }
    }

    private void doRemove(Node deleted){
        Node replaced=findReplaceed(deleted);
        Node parent=deleted.parent;
        //没有孩子了
        if(replaced==null){
            //case1：删除的是根节点
            if(deleted==root){
                root=null;
            }else{
                if(isBlack(deleted)){
                    //复杂调整
                    fixDoubleBlack(deleted);
                }else{
                    //红色叶子无需任何调整
                }
                if(deleted.isLeftChild()){
                    parent.left=null;
                }else{
                    parent.right=null;
                }
                deleted.parent=null;//help GC
            }
            return;
        }
        //只有一个孩子
        if(deleted.left==null || deleted.right==null){
            //case1：删除的是根节点
            if(deleted==root){
                root.key=replaced.key;
                root.value=replaced.value;
                root.left=root.right=null;
            }else {
                if(deleted.isLeftChild()){
                    parent.left=replaced;
                }else{
                    parent.right=replaced;
                }
                replaced.parent=parent;
                deleted.left=deleted.right=deleted.parent=null;//help GC
                if(isBlack(deleted) && isBlack(replaced)){
                    //复杂处理
                    fixDoubleBlack(replaced);
                }else{
                    //case2:删的是红色，剩下的时黑色，把剩下的变成黑色即可
                    replaced.color=BLACK;
                }
            }
            return;
        }
        //case0：有两个孩子，要把这种情况转换为一个或者没有孩子
        //换值
        int t=deleted.key;
        deleted.key=replaced.key;
        replaced.key=t;

        //换颜色
        Object v=deleted.value;
        deleted.value=replaced.value;
        replaced.value=v;
        //最后把换下来的删除就行了
        doRemove(replaced);
    }

    //查找到被删除节点
    Node find(int key){
        Node p=root;
        while(p!=null){
            if(key<p.key){
                p=p.left;
            }else if(p.key<key){
                p=p.right;
            }else{
                return p;
            }
        }
        return null;
    }

    //查到到剩余节点
    Node findReplaceed(Node deleted){
        if(deleted.left==null && deleted.right==null){
            return null;
        }
        if(deleted.left==null){
            return deleted.right;
        }
        if(deleted.right==null){
            return deleted.left;
        }
        //两个孩子都有，实际上返回的就是后继节点
        Node s=deleted.right;
        while(s.left!=null){
            s=s.left;
        }
        return s;
    }


}
